<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        排队找零问题可以用贪心算法求解，具体步骤如下：
                    </div>
                    <div>
                        1.将所有的硬币面值从大到小排序。
                    </div>
                    <div>
                        2.对于待找零的金额，从大到小依次考虑每种面值的硬币，
                    </div>
                    <div>
                        3.如果当前面值的硬币可以找零，则尽可能多地使用该面值的硬币，直到无法再找零为止。
                    </div>
                    <div>
                        4.如果当前面值的硬币不能找零，则考虑下一种面值的硬币。
                    </div>
                    <div>
                        5.如果到最后一种面值的硬币也无法找零，则回溯到上一个加入的硬币，换成之后一个面值的硬币。
                    </div>
                    <div>
                        6.重复步骤3和4、5，直到找零完成。
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <!-- <el-image style="width:100%" :src="url" :fit="fit" loading="lazy"></el-image> -->
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                        #include &lt;cstdio>  
                            #include &lt;algorithm>  
                            using namespace std;
                            int A;   
                            int ans=0;     //所需硬币总数  
                            int ret[6]={0}; //所需每种硬币的数量   
                            int moneycnt[6];//现有6种硬币的数量   
                            int moneyval[6]={1,5,10,50,100,500};//每种硬币的面值   
                            int main()  {  
                                int i;  
                                int temp;  
                                scanf("%d",&A);  
                                for(i=0;i&lt;6;i++)  
                                      scanf("%d",moneycnt[i]);    
                                for(i=5;i>=0;i--) {     //贪心策略：优先选择面值大的硬币    
                                         temp=min(A/moneyval[i],moneycnt[i]); //temp记录使用硬币i的枚数，注意不能超过moneycnt[i]    
                                         A-=(temp*moneyval[i]);    //剩余支付金额 
                                         ret[i]+=temp;      //使用硬币i的枚数+temp
                                         ans+=temp;         //已使用的硬币数+temp     
                                  }    
                                if(A>0) //A>0表示无法用现有硬币支付A元，故输出-1    
                                     printf("-1\n");      
                                else {   //其它情况：可完成支付       
                                    printf("%d\n",ans);  //最少硬币数     
                                    for(i=0;i&lt;6;i++)  //每种硬币需要的数量   
                                        printf("%d 元: %d\n",moneyval[i],ret[i]);  
                                }  
                                return 0;  
                            } 
                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                        <code>
                            def getMinCoinCountBackTracking(total, values):
                                if (len(values) == 0):
                                    return -1
                                # 当前币值
                                currentCoin = values[0]
                                # 使用当前币值的数量
                                useCurrentCoinCount = total // currentCoin
                                restTotal = total - useCurrentCoinCount * currentCoin
                                # 如果restTotal为0，表示余额已除尽，组合完成
                                if (restTotal == 0):
                                    return useCurrentCoinCount

                                # 其他币种数量
                                coinCount = -1
                                # 剩余的币种
                                restCoins = values[1 :]
                                while (useCurrentCoinCount >= 0):
                                    # 尝试用剩余面值求当前余额的硬币总数
                                    coinCount = getMinCoinCountBackTracking(restTotal, restCoins)
                                    # 如果后续没有有可用组合，退一步，当前useCurrentCoinCount币数减1
                                    if (coinCount == -1):
                                        useCurrentCoinCount -= 1
                                        restTotal = total - useCurrentCoinCount * currentCoin
                                    else:
                                        return useCurrentCoinCount + coinCount
                                return -1

                            def main():
                                values = [5, 3]
                                total = 11
                                result = getMinCoinCountBackTracking(total, values)
                                print(result)

                            if __name__ == "__main__":
                                main()
                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                      <code>
                        package SF;
 
                        public class 找零钱问题 {
	                        int i;
	                        static int n = 5;
	                        double m = 0.09;
	                        double m1 = 0.09;
	                        //主函数
	                        public static void main(String[] args) {
		                        double[] V = new double[]{1,0.5,0.1,0.05,0.02,0.01};
		                        int[] X = new int[6];
		                        找零钱问题 p = new 找零钱问题();
		                        X=p.Greedy(V);
		                        int s = X[0]+X[1]+X[2]+X[3]+X[4]+X[5];
		                        System.out.println("得到找零钱问题的最优解为：X = { "+X[0]+" "+X[1]+" "+X[2]+" "+X[3]+" "+X[4]+" "+X[5]+" }共需要最少"+s+"枚硬币。");
	                        }
	                        //贪心算法-找零问题
	                        int[] Greedy(double C[]){
		                        int i=0;
		                        double x = 0;
		                        double[] S = new double[n+1];
		                        int[] Z = new int[n+1];
		                        for(i=0;i&lt;=n;i++){
			                        if( solution(S)==0 ){
				                        x = select(C);
				                        if (feasible(S,x)==1)
				                        {
					                        S[i] = x;
					                        Z[this.i]++;
					                        m1 = ((double)((int)(m1*100) - (int)(x*100)))/100;
				                        }
			                        }
		                        }System.out.println("使用硬币集为：{ "+S[0]+"  "+S[1]+"  "+S[2]+" }");
		                        return Z;
	                        }
	                        //解决函数 solution
	                        int solution(double X[]){
		                        double s = 0;
		                        for(int i=0;i&lt;=n;i++){
			                        s=((double)(int)(s*100)+(int)(X[i]*100))/100;
		                        }
		                        if(s==m)
			                        return 1;
		                        else
			                        return 0;
	                        }
	                        //选择函数 select
	                        double select(double X[]){
		                        int i = 0;
		                        double x = 0;
		                        do{X[i]=0;i++;}
		                        while(X[i]>m1||X[i]==0);
		                        this.i = i;
		                        x = X[i];
		                        return x;
	                        }
	                        //可行函数 feasible
	                        double feasible(double X[],double x){
		                        int i;
		                        int j=1;
		                        double y=0;
		                        for(i=0;i&lt;=n;i++){
			                        y=y+X[i];
		                        }
		                        y=y+x;
		                        return j;
	                        }
                        }
                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>
